'''
单调队列： 单调(队列+栈)

经典功能：   https://leetcode.cn/problems/sliding-window-maximum/
    实现滑动窗口中，每一步获得当前窗口内的最大值

    最小值同理


其他宽限的用法：
1.有单调性
2.从队尾进入队列，淘汰队头，队尾元素
3. 淘汰时，统计答案，且后续肯定无关了
'''
from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        result = [0] * (n - k + 1)
        queue = deque()     # 从左往右，从大到小； 想获得当前最大值从左看，
                            # 左边元素，是先进去的，也会成为先淘汰的
                            # 右边元素，是后进去的，可能是之后的最大值
        for i in range(k - 1):
            while queue and nums[i] > nums[queue[-1]]:
                queue.pop()
            queue.append(i)

        # 窗口：k~i, 窗口大小k
        for l, r in enumerate(range(k - 1, n)):
            while queue and nums[r] > nums[queue[-1]]:
                queue.pop()
            queue.append(r)
            result[l] = nums[queue[0]]

            # 窗口还要缩小
            if queue[0] == l:
                queue.popleft()
        return result

